package com.squirrel.michale;

import java.util.HashMap;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/14 7:26 AM
 * @company Michale Squirrel
 * @link
 * @description
 * 2196. 根据描述创建二叉树
 * 中等
 * 30
 * 相关企业
 * 给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：
 *
 * 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
 * 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。
 * 请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
 *
 * 测试用例会保证可以构造出 有效 的二叉树。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
 * 输出：[50,20,80,15,17,19]
 * 解释：根节点是值为 50 的节点，因为它没有父节点。
 * 结果二叉树如上图所示。
 */
public class LeetCode2196 {

    public TreeNode createBinaryTree(int[][] descriptions) {
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
        HashMap<Integer, TreeNode> nodeMap = new HashMap<>();
        for (int i = 0; i < descriptions.length; i++) {
            int[] description = descriptions[i];
            TreeNode treeNode = new TreeNode(description[0]);
            nodeMap.put(description[1], treeNode);
            if (description[2] == 1) {
                treeNode.left = new TreeNode(description[1]);
                nodeMap.put(description[1], treeNode.left);
                parentMap.put(treeNode.left, treeNode);
            } else if (description[2] == 0) {
                treeNode.right = new TreeNode(description[1]);
                nodeMap.put(description[1], treeNode.right);
                parentMap.put(treeNode.right, treeNode);
            }
        }
        for (TreeNode node : parentMap.keySet()) {
            if (parentMap.get(node) == null) {
                return node;
            }
        }
        return null;
    }


    public TreeNode createBinaryTree2(int[][] descriptions) {
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
        HashMap<Integer, TreeNode> nodeMap = new HashMap<>();
        for (int i = 0; i < descriptions.length; i++) {
            int[] description = descriptions[i];
            TreeNode treeNode;
            if (nodeMap.get(description[0]) == null) {
                treeNode = new TreeNode(description[0]);
                nodeMap.put(description[0], treeNode);
            }else {
                treeNode = nodeMap.get(description[0]);
            }

            if (description[2] == 1) {
                TreeNode left;
                if (nodeMap.get(description[1]) == null) {
                    left = new TreeNode(description[1]);
                } else {
                    left = nodeMap.get(description[1]);
                }
                treeNode.left = left;
                nodeMap.put(description[1], treeNode.left);
                parentMap.put(treeNode.left, treeNode);
            } else if (description[2] == 0) {
                TreeNode right;
                if (nodeMap.get(description[1]) == null) {
                    right = new TreeNode(description[1]);
                } else {
                    right = nodeMap.get(description[1]);
                }
                treeNode.right = right;
                nodeMap.put(description[1], treeNode.right);
                parentMap.put(treeNode.right, treeNode);
            }
        }
        for (Integer integer : nodeMap.keySet()) {
            TreeNode node = nodeMap.get(integer);
            if (parentMap.get(node) == null) {
                return node;
            }
        }
        return null;
    }

    public static void main(String[] args) {

        LeetCode2196 leetCode2196 = new LeetCode2196();

        int[][] descriptions = new int[][]{{20, 15, 1}, {20, 17, 0}, {50, 20, 1}, {50, 80, 0}, {80, 19, 1}};

//        输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
//        输出：[50,20,80,15,17,19]
//        解释：根节点是值为 50 的节点，因为它没有父节点。
//        结果二叉树如上图所示。

        TreeNode treeNode = leetCode2196.createBinaryTree2(descriptions);
        System.out.println(treeNode.val);


//        输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
//        输出：[1,2,null,null,3,4]
//        解释：根节点是值为 1 的节点，因为它没有父节点。
//        结果二叉树如上图所示

        int[][] descriptions2 = new int[][]{{1,2,1}, {2,3,0}, {3,4,1}};

        TreeNode treeNode2 = leetCode2196.createBinaryTree2(descriptions2);
        System.out.println(treeNode2.val);

    }



}
